package com.cbd.basic.algorithm.sort;

import com.alibaba.fastjson.JSON;
import lombok.extern.slf4j.Slf4j;

/**
 * 快速排序
 * 核心思想：选择基准，一般为中间位置，然后进行分区，将基准
 * 时间复杂度：O(n²)
 */
@Slf4j
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        quickSort(array, 0, array.length - 1);
        log.info("after sorted array = {}", JSON.toJSONString(array));
    }

    private static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            // 递归排序
            quickSort(array, low, pivotIndex);
            quickSort(array, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] array, int low, int high) {
        // 选择中间元素作为基准
        int pivot = array[low + (high - low) / 2];
        int i = low - 1;
        int j = high + 1;

        while (true) {
            // 从左向右找到第一个大于等于基准的元素
            do {
                i++;
            } while (array[i] < pivot);

            // 从右向左找到第一个小于等于基准的元素
            do {
                j--;
            } while (array[j] > pivot);

            // 如果指针相遇，返回分区点
            if (i >= j) {
                return j;
            }

            // 交换元素
            swap(array, i, j);
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
